package com.nuo.laboratory.dataStructure;

import java.util.*;

/**
 * @author LGC
 * @date 2022/4/1 14:16
 */
public class MyQueue {

    /**
     * 完全平方数相加最少个数
     * 12
     * 0+1 0+4 0+9 0+16
     * 0+1+1 0+1+4 0+1+9 0+4+1 0+4+1 0+4+4 0+4+9
     * 0+1+1+1 0+1+1+4 0+1+1+9  0+1+4+1 0+1+4+4 0+1+4+9 0+1+9+1 0+1+9+4 0+4+1+1 0+4+1+4 0+4+1+9 0+4+4+1 0+4+4+4
     */
    public int getMinCount(int n) {
        Queue<Integer> queue = new LinkedList<>();
        // 保存已遍历的节点值
        Set<Integer> set = new HashSet<>();
        queue.offer(0);
        set.add(0);
        int num = 0;
        while (!queue.isEmpty()) {
            num++;
            // 每一层节点数量
            int size = queue.size();
            // 遍历当前层的所有节点
            for (int i = 0; i < size; i++) {
                // 当前节点值
                int rs = queue.poll();
                // 访问当前节点的子节点，类比于二叉树的左右子节点
                for (int j = 1; j <= Math.sqrt(n); j++) {
                    // 子节点的值
                    int nodeValue = rs + j * j;
                    // 如果大于n，终止内层循环
                    if (nodeValue > n) {
                        break;
                    }
                    // nodeValue始终是完全平方数的和，当他等于n的时候直接返回
                    if (nodeValue == n) {
                        return num;
                    }
                    // 除去值相同插入 如 1+4 4+1
                    if (!set.contains(nodeValue)) {
                        queue.offer(nodeValue);
                        set.add(nodeValue);
                    }
                }
            }
        }
        return num;
    }


    /**
     * 打开转盘锁
     * 给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1
     * 初始值 0000
     * p输入：deadends =["0201","0101","0102","1212","2002"],target ="0202"
     * 输出：6
     */
    public int openLock(String[] deadends, String target) {
        Set<String> set = new HashSet<>(Arrays.asList(deadends));
        //开始遍历的字符串是"0000"，相当于根节点
        String startStr = "0000";
        if (set.contains(startStr)) {
            return -1;
        }
        int level = 0;
        Queue<String> queue = new LinkedList<>();
        Set<String> history = new HashSet<>();
        queue.offer(startStr);
        history.add(startStr);
        while (!queue.isEmpty()) {
            // 当前队列元素数量
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String nodeVal = queue.poll();
                if (nodeVal.equals(target)) {
                    return level;
                }
                for (int j = 0; j < 4; j++) {
                    /**
                     * j = 0   '' +'1' + '000'    '' +'9' + '000'
                     * j = 1   '0' +'1' + '00'    '0' +'9' + '00'
                     * j = 2   '00' +'1' + '0'    '00' +'9' + '0'
                     * j = 3   '000' +'1' + ''    '000' +'9' + ''
                     */
                    char charAt = nodeVal.charAt(j);
                    String addStr = nodeVal.substring(0, j) + (charAt == '9' ? 0 : charAt - '0' + 1) + nodeVal.substring(j + 1);
                    String subStr = nodeVal.substring(0, j) + (charAt == '0' ? 9 : charAt - '0' - 1) + nodeVal.substring(j + 1);
                    if (!set.contains(addStr) && !history.contains(addStr)) {
                        queue.offer(addStr);
                        history.add(addStr);
                    }
                    if (!set.contains(subStr) && !history.contains(subStr)) {
                        queue.offer(subStr);
                        history.add(subStr);
                    }
                }
            }
            level++;
        }
        return -1;
    }

    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        String[] deadends = new String[]{"0201", "0101", "0102", "1212", "2002"};
        String target = "0202";
        int i = myQueue.openLock(deadends, target);
        System.out.println(i);
//
//        System.out.println('8' + 1);
//        System.out.println('8' + 0);
//        System.out.println('0' + 0);
//        System.out.println(57 - 48);
//
//        System.out.println( "1234".substring(4));

    }


}
